package common;

import com.sun.tools.javac.Main;

import java.util.ArrayList;

public class quickSort {
    public <Val extends Comparable<Val>> ArrayList<Val> run(ArrayList<Val> vals) {
        if (vals.size() <= 1) {
            return vals;
        }

        Val mark = vals.get(0);
        ArrayList<Val> left = new ArrayList<>();
        ArrayList<Val> right = new ArrayList<>();
        for (int i = 1; i < vals.size(); i++) {
            if (vals.get(i).compareTo(mark) <= 0) {
                left.add(vals.get(i));
            } else {
                right.add(vals.get(i));
            }
        }

        ArrayList<Val> newVals = new ArrayList<>(run(left));
        newVals.add(mark);
        newVals.addAll(run(right));

        return newVals;
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(33);
        arr.add(4);
        arr.add(43);
        arr.add(23);
        arr.add(33);
        arr.add(234);
        arr.add(5);

        quickSort sort = new quickSort();
        sort.run(arr);

        System.out.println(sort.run(arr));
    }
}
